﻿# Raycaster.py: ray-casting module
# Written by Victor Luna Freire - victorclf@live.com
# Copyright (c) Victor Luna Freire. All rights reserved.
# Sunday, May 26, 2009 00:00:00 PM
# Python 2.6.2

import math
import pygame
import copy
import os
from warnings import *
import random #for testing

from Textures import * #imports Textures instance
from Maps import *
import Defines
import Gameobjects #testing purposes
import Sprites
import Renderer

# Coordinate System
#
#  0 - - - - - - - >  X
#  |
#  |
#  |
#  |
#  |
#  V
#
#  Y

# NOTE: X actually represents the COLUMNS and Y the LINES, so to access the desired point the world we use:
# world[y][x] - (x and y being in matrix(grid) notation)

# ASSERTS: optimization, compile with -O (only asserts removed) or -OO(asserts and doc strings removed) flags

# OPTIMIZATION NOTE: changing the cube size from 128 will result in unexpected behavior due to some optimizations

class Slice:
    def __init__(self, x, obj_dist, obj_surface, obj_width, offset):
        self.x = x
        self.obj_dist = obj_dist
        self.obj_surface = obj_surface
        self.obj_width = obj_width
        self.offset = offset


class RaycasterClass:
    def __init__(self, screen_width=320, screen_height=200):
        self.SCREEN_WIDTH = Defines.PROJECTION_WIDTH
        self.SCREEN_HEIGHT = Defines.PROJECTION_HEIGHT

        # World constants
        self.CUBE_SIZE = Defines.CUBE_SIZE  # size of the world's cubes
        self.PLAYER_HEIGHT = Defines.PLAYER_HEIGHT
        self.FOV = Defines.FOV
        
        self.SCREEN_DISTANCE = self.SCREEN_WIDTH / (2*math.tan(math.radians(self.FOV/2))) # distance to projection plane
        self.ANGLE_BETWEEN_RAYS = self.FOV / self.SCREEN_WIDTH   # angle between subsequent rays
           
        assert isinstance(self.FOV, float)
        assert isinstance(self.ANGLE_BETWEEN_RAYS, float)
        assert self.ANGLE_BETWEEN_RAYS
           
        self.SLICE_HEIGHT_CONSTANT = self.CUBE_SIZE * self.SCREEN_DISTANCE #constant used in the slice height calculation
        self.SLICE_COLOR = (0, 0, 255) #untextured slices
        self.slice_piece_temp = pygame.Surface((1, self.CUBE_SIZE)).convert() #holds the slice piece for each drawn slice
        self.slice_piece_temp.set_colorkey((255,0,255), 0)
        
        self.NO_TEXTURES = False
        
        # The wall texture identifiers, relates the numbers in the array to the texture
        self.WALL_IDS_LIST_PATH = os.path.join(os.curdir, "data", "wallids.dat")
        self.WALL_TEXTURE_IDS = {} #wall symbol -> texture name
        
        
        # code to help debugging the Raycaster
        self.grid_surface_enabled = False
        self.grid_surface = None
        self.grid_wall_color = (255, 0, 0)
        self.grid_scale = 1
        self.grid_draw_rays = False

        self.store_ray_debug_info = False
        self.rays_info = ''
        
        # Load textures
        Textures.load_textures()
        # Load wall symbols(ids) -- wall symbol is used to find the corresponding texture name
        self.load_wall_ids()
        
    
    
    def object_intersect(self, povv, objj, ray_angle, obj_width):
        '''
        Calculates the distance and the texture offset of a given object. If the ray hits the object.
        Returns the tuple (distance, offset)
        '''
        #MONSTER LINE SEGMENT: (always perpendicular to player view angle)
        #B ----------- O ------------ A
        #
        #O == obj.pos
        ob_angle = ray_angle + 90
        obj = PointOfView(objj.x, -objj.y, objj.angle)
        pov = PointOfView(povv.x, -povv.y, povv.angle)
        
        m_ob = math.tan(math.radians(ob_angle))
        m_ra = math.tan(math.radians(ray_angle))
        
        # Intersection point coordinates
        if m_ob == m_ra: return None #prevent zero division
        x = (-m_ra * pov.x + m_ob * obj.x + pov.y - obj.y) / (m_ob - m_ra)
        y = m_ra*(x - pov.x) + pov.y
        
        # Is the intersection point valid?
        ## Get coordinate boundaries for intersection point
        obvec = ((obj_width/2) * math.cos(math.radians(ob_angle)), (obj_width/2) * math.sin(math.radians(ob_angle)))
        b = (obj.x + obvec[0], obj.y + obvec[1])
        a = (obj.x - obvec[0], obj.y - obvec[1])
        
        min_x = a[0] if a[0] < b[0] else b[0]
        max_x = a[0] if a[0] > b[0] else b[0]
        min_y = a[1] if a[1] < b[1] else b[1]
        max_y = a[1] if a[1] > b[1] else b[1]
        assert min_x == min(a[0], b[0])
        assert min_y == min(a[1], b[1])
        assert max_x == max(a[0], b[0])
        assert max_y == max(a[1], b[1])
                                
        #self.debug_points.append((obj.x, -obj.y))
        if not(min_x <= x <= max_x and min_y <= y <= max_y):
            return None
        
        distance = self.distance_points((x, y), (pov.x, pov.y), ray_angle)
        offset = self.distance_points((x, y), (b[0], b[1]), ob_angle)
        
        #Apply fishbowl correction
        corrected_distance = self.correct_distance(pov, (x, y), ray_angle, distance)
        
        return (corrected_distance, offset)
                                            
        
    
    def load_wall_ids(self):
        try:
            f = open(self.WALL_IDS_LIST_PATH)
        except:
            print "Error: failed to load - %s" % self.WALL_IDS_LIST_PATH
            raise SystemExit
        
        line_number = 1
        for i in f.readlines():
            if i.isspace(): continue
            
            info = i.split()
            
            if len(info) != 2:
                warn("wallids list, invalid entry on line %d, ignoring..." % line_number)
                continue
            
            if info[0] in self.WALL_TEXTURE_IDS:
                warn("Wall symbol being redefined: %s - %s" % (info[0], info[1]))
            
            self.WALL_TEXTURE_IDS[info[0]] = info[1]
            
            line_number += 1
        
        f.close()
        
        

    def get_screen_size(self):
        ''' Gets the size of the rendering screen. '''
        return (SCREEN_WIDTH, SCREEN_HEIGHT)


    def toggle_ray_debug_info(self, enable):
        self.store_ray_debug_info = enable
        

    def toggle_grid_surface(self, enable):
        return False
        ''' Toggles the creation of a grid surface during each scene. '''
        if enable and not self.grid_surface_enabled:
            self.grid_surface_enabled = True
            return True
        self.grid_surface_enabled = False
        self.grid_surface = None
        return False
    
        
    def toggle_textures(self, enable):
        self.NO_TEXTURES = not enable
        return enable
    
    
    def set_grid_scale(self, scale):
        return False
        ''' Sets a new scale for the world grid. '''
        if not self.grid_surface_enabled: warn("Warning: grid surface not enabled!")
        self.grid_scale = scale
        

    def draw_point_grid(self, pos, size=4,color=(255, 255, 0)):
        return False
        ''' Draws a point on the 2D grid of the world. '''
        if not self.grid_draw_rays:
            return False
        if not self.grid_surface:
            warn("Warning: tried to draw point to grid when it was not requested!")
            return False
        self.grid_surface.fill(color, (pos[0] * self.grid_scale - (size/2), pos[1] * self.grid_scale - (size/2), size, size))
        return True
    
    def draw_ray_grid(self, pov, pos):
        return False
        ''' Draws a ray from the player's on the 2D grid of the world. '''
        if not self.grid_draw_rays:
            return False
        if not self.grid_surface:
            warn("Warning: tried to draw ray to grid when it was not requested!")
            return False
        pygame.draw.line(self.grid_surface, (0, 0, 255) , (pov.x * self.grid_scale, pov.y * self.grid_scale), (pos[0] * self.grid_scale, pos[1] * self.grid_scale))
        return True
    
    
    def draw_line_grid(self, pos1, pos2):
        return False
        ''' Draws a ray from the player's on the 2D grid of the world. '''
        if not self.grid_draw_rays:
            return False
        if not self.grid_surface:
            warn("Warning: tried to draw ray to grid when it was not requested!")
            return False
        pygame.draw.line(self.grid_surface, (0, 255, 0) , (pos1[0] * self.grid_scale, pos1[1] * self.grid_scale), (pos2[0] * self.grid_scale, pos2[1] * self.grid_scale))
        return True
    
    def get_grid_surface():
        return False
        return self.grid_surface
          
    
    def create_world_grid(self):
        return False
        ''' Creates a 2D grid of the world. '''
        if not self.grid_surface:
            horizontal_scale = float(self.SCREEN_WIDTH) / (Maps.world_bounds[0] * self.CUBE_SIZE)
            vertical_scale = float(self.SCREEN_HEIGHT) / (Maps.world_bounds[1] * self.CUBE_SIZE)
            self.set_grid_scale(min((horizontal_scale, vertical_scale)))
            self.grid_surface = pygame.surface.Surface((self.CUBE_SIZE * self.grid_scale * Maps.world_bounds[0],
                                                        self.CUBE_SIZE * self.grid_scale * Maps.world_bounds[1])).convert()
        self.grid_surface.fill((0,0,0))  #clears grid_surface
        for x in xrange(Maps.world_bounds[0]):
            for y in xrange(Maps.world_bounds[1]):
                newrect = pygame.rect.Rect(x * self.CUBE_SIZE * self.grid_scale,
                                           y * self.CUBE_SIZE * self.grid_scale,
                                           self.CUBE_SIZE * self.grid_scale, self.CUBE_SIZE * self.grid_scale)
                if Maps.world[y][x] != '0':
                    pygame.draw.rect(self.grid_surface, (255,255,255), newrect, 1)
                    boxrect = pygame.rect.Rect(x * self.CUBE_SIZE * self.grid_scale + 1,
                                               y * self.CUBE_SIZE * self.grid_scale + 1,
                                               self.CUBE_SIZE * self.grid_scale - 2,
                                               self.CUBE_SIZE * self.grid_scale - 2)
                    self.grid_surface.fill(self.grid_wall_color, boxrect)
                    
                else:
                    pygame.draw.rect(self.grid_surface, (255,255,255), newrect, 1)
        
        
    
    def set_screen_size(self, size):
        '''Sets the size of the rendering screen '''
        self.SCREEN_WIDTH = size[0]
        self.SCREEN_HEIGHT = size[1]
    
    
    def togrid(self, pos):
        # TODO: Redundancy. Use the functions in Shared.py?
        ''' Converts from unit coordinate to grid coordinate. '''
        #return int(pos[0] / self.CUBE_SIZE), int(pos[1] / self.CUBE_SIZE)
        assert not isinstance(pos[0], float)
        assert not isinstance(pos[1], float)
        return (pos[0] >> 7, pos[1] >> 7)

    
    def togridF(self, pos):
        ''' Converts from unit coordinate to grid coordinate. Casts to int! '''
        return (int(pos[0]) >> 7, int(pos[1]) >> 7)
        
    
    def wall_on(self, gridpos):
        ''' Checks for wall on grid coordinates X and Y '''
        return Maps.world[gridpos[1]][gridpos[0]] != '0'


    def distance_points(self, p1, p2, angle):
        if 45 < (angle % 180) < 135:
            return abs((p1[1] - p2[1]) / math.sin(math.radians(angle)))
        return abs((p1[0] - p2[0]) / math.cos(math.radians(angle)))
        
            
    def nearest_point_and_dist(self, pov, angle, h_intersect, v_intersect):
        ''' Returns the nearest point of the two and the distance to it. 0 means the first is closer and 1 the second is. '''
        #TODO: reuse distance_points? any slowdown in this?
        if h_intersect:
            if 45. < (angle % 180) < 135.:
                h_dist = abs((pov.y - h_intersect[1]) / math.sin(math.radians(angle)))
            else:
                h_dist = abs((pov.x - h_intersect[0]) / math.cos(math.radians(angle)))
        if v_intersect:
            if 45. < (angle % 180) < 135.:
                v_dist = abs((pov.y - v_intersect[1]) / math.sin(math.radians(angle)))
            else:
                v_dist = abs((pov.x - v_intersect[0]) / math.cos(math.radians(angle)))
            
        if h_intersect and v_intersect:
            if h_dist < v_dist:
                v_intersect = None
            else:
                h_intersect = None
                
        if h_intersect:
            nearest_point = False
            true_dist = h_dist
        else: #elif v_intersect:
            nearest_point = True
            true_dist = v_dist
        
        return (nearest_point, true_dist)
    
    
    def correct_distance(self, pov, angle, true_distance): # h_intersect, v_intersect):
        ''' Returns the distance to a wall. '''
        # Calculates the correct distance, removes the "fishbowl" distortion
        
        # fishbowl effect correction
        angle_view_and_ray = (pov.angle - angle) % 360  #angle between the view angle and the ray
        correct_distance = abs(true_distance * math.cos(math.radians(angle_view_and_ray)))
        
        return correct_distance

        
    def texture_offset(self, point, is_v_intersect, ray_angle):
        if is_v_intersect:
            texoffset = (point[1] % self.CUBE_SIZE)
            #if 180 < ray_angle < 360:
            #    texoffset = self.CUBE_SIZE - 1 - (point[1] % self.CUBE_SIZE)
        else:
            texoffset = (point[0] % self.CUBE_SIZE)
            #if 180 < ray_angle < 360:
            #    texoffset = self.CUBE_SIZE - 1 - (point[0] % self.CUBE_SIZE)
                    
        return texoffset
        

    def slice_height(self, distance):
        ''' Returns the height of a wall slice based on the distance to it. '''
        if not distance: return self.CUBE_SIZE
        return self.SLICE_HEIGHT_CONSTANT / distance
    
    
    def get_wall_id(self, wallpoint):
        gridpos = self.togridF(wallpoint)
        return Maps.world[gridpos[1]][gridpos[0]]
        
    
    def get_texture_name(self, wallid):
        try:
            return self.WALL_TEXTURE_IDS[wallid]
        except KeyError:
            warn(("Unknown wall id: %s, using default texture" % wallid))
            return "1"
        
            
    def draw_slice(self, dest, x, wall_dist, surface, texture_width, offset):
        # WALL SLICE DRAWING
        # Calculate slice parameters
        slice_h = int(self.slice_height(wall_dist))
        if slice_h > 60000: #avoid overflow crashes
            slice_h = 60000
            
        slice_y1 = (self.SCREEN_HEIGHT - slice_h) / 2
        slice_y2 = slice_y1 + slice_h
        
        #REMOVED FOR MAXIMUM SPEED
        # Finally, draw the slice on the screen
        #if self.NO_TEXTURES or not surface:
        #    pygame.draw.line(dest, self.SLICE_COLOR, (x, slice_y1), (x, slice_y2))
        #else:
        self.slice_piece_temp.fill((255, 0, 255))
        self.slice_piece_temp.blit(surface, (0, 0),
                                   (offset, 0, offset+1, surface.get_height()))
        
        slicescaled = pygame.transform.scale(self.slice_piece_temp, (1, slice_h))
        dest.blit(slicescaled, (x, slice_y1))
        
        
    def render_scene(self, dest, pov, all_objects):
        '''
        Renders map to a surface

        dest - surface to draw on
        pov - player point of view
        '''
        
        assert Maps.world, "Tried to render a scene without loading the world first!"
        assert Maps.world_bounds[0], "Invalid world_bounds[0]"
        assert Maps.world_bounds[1], "Invalid world_bounds[1]"
        
        somethingdraw = False

        if self.store_ray_debug_info:
            self.rays_info = 'player view angle: %f\n' % pov.angle
        
        if self.grid_surface_enabled: self.create_world_grid()
        
        ray_angle = pov.angle + (self.FOV/2)

        if self.store_ray_debug_info:
            self.rays_info = 'player view angle: %f\n' % pov.angle
            self.rays_info += 'first original ray angle: %f\n' % ray_angle
                    
        # Draw solid ceiling
        dest.fill((40, 40, 40), (0, 0, self.SCREEN_WIDTH, self.SCREEN_HEIGHT/2))
        
        # Draw solid floor
        dest.fill((70, 70, 70), (0, self.SCREEN_HEIGHT/2, self.SCREEN_WIDTH, self.SCREEN_HEIGHT/2))
                
        objects = sorted([(Renderer.distance_points(o.x, o.y, pov.x, pov.y), o) for o in all_objects], reverse=True)
        self.enemies_in_aim = []
        
        # Scan screen left to right
        for x in xrange(self.SCREEN_WIDTH):   
            # IMPORTANT: even though we're dealing with angles from 0-360, angles>360 are not interpreted as we may think
            # Erratic behaviour succeeds with angles higher than 360, e.g: math.radians(28) != math.radians(388)
            # This line below only works due to Python's characteristic remainder behaviour, for other languages such as
            # C++ use if ray_angle < 0: ray_angle += 360 else ray_angle %= 360
            ray_angle %= 360
                                    
            #h_hit = self.horizontal_intersect((pov.x, pov.y), ray_angle)
            #v_hit = self.vertical_intersect((pov.x, pov.y), ray_angle)
            h_hit = Renderer.horizontal_intersect(pov.x, pov.y, ray_angle, Maps.world_bounds[0], Maps.world_bounds[1], Maps.world)
            v_hit = Renderer.vertical_intersect(pov.x, pov.y, ray_angle, Maps.world_bounds[0], Maps.world_bounds[1], Maps.world)
                    
            if self.store_ray_debug_info:
                self.rays_info += '%d - %f:\n ' % (x, ray_angle)
                if h_hit: self.rays_info += 'h_hit (%d, %d) -- ' % h_hit
                if v_hit: self.rays_info += 'v_hit (%d, %d)    ' % v_hit
                self.rays_info += '\n'
                
            if not(h_hit[0] < 0 and v_hit[0] < 0):
                is_v_closer, true_dist = Renderer.nearest_point_and_dist(pov.x, pov.y, ray_angle, h_hit[0], h_hit[1], v_hit[0], v_hit[1])
                closer_point = v_hit if is_v_closer else h_hit
                texoffset = self.texture_offset(closer_point, is_v_closer, ray_angle)
                #wall_dist = self.correct_distance(pov, ray_angle, true_dist) # the correct distance
                wall_dist = Renderer.correct_distance(pov.x, pov.y, pov.angle, ray_angle, true_dist) # the correct distance
                               
                if self.grid_surface: self.draw_ray_grid(pov, closer_point)
                
                
                if wall_dist:
                    somethingdraw = True
                    wallid = self.get_wall_id(closer_point)
                    texname = self.get_texture_name(wallid)
                    wall_surface = Textures.get_texture(texname)
                    self.draw_slice(dest, x, wall_dist, wall_surface, self.CUBE_SIZE, texoffset)
                
                ##OBJECT DRAWING
                #o[0] is the distance between the centers
                for o in objects:
                    if o[0] <= wall_dist:
                        obj_surface = Sprites.Sprites.sprites_surfaces[o[1].surface_name]
                        obj_width = obj_surface.get_width()
                                                                        
                        #&pov.x, &pov.y, &obj.x, &obj.y, &ray_angle, &view_angle, &obj_width)
                        obj_intersect = Renderer.object_intersect(pov.x, pov.y, o[1].x, o[1].y, ray_angle, pov.angle, obj_width)
                        
                        if obj_intersect:
                            obj_dist, offset = obj_intersect
                            self.draw_slice(dest, x, obj_dist, obj_surface, obj_width, offset)
                            if x in (305, 325, 345):
                                if o[1].health > 0:
                                    self.enemies_in_aim.append((o))
                                
                    #else:
                        #print o[0], '--', wall_dist
                
                #if slices:
                #    slices.sort();
                #    for s in reversed(slices):
                #        self.draw_slice(dest, *s[1]) #obsolete comment: draws the closest slice
                    
                    #DEBUG
                    #for o in objects:
                    #    obj_surface = o.get_surface()
                    #    obj_width = obj_surface.get_width()
                    #    odist_offset  = self.object_intersect(pov, ray_angle, o, obj_width, False)
                    #                            
                    #    if odist_offset:
                    #        odist, offset = odist_offset
                    #        #if self.grid_surface: odist = self.object_intersect(pov, ray_angle, o, obj_width, True)
                    #        #else: odist = self.object_intersect(pov, ray_angle, o, obj_width, False)
                    #        
                    #        if odist < wall_dist:
                    #            if self.grid_surface_enabled and x == 0:
                    #                assert self.grid_surface    
                    #            self.draw_slice(dest, x, odist, obj_surface, obj_width, offset)
                    #            
                    #            
                    #            #self.draw_slice(dest, x, odist, None, obj_width, 0) -- #untextured
                    #            
                    #            #print 'wall_dist:', wall_dist
                    #            #print '************'
                    #            #print 'obj_surface:', obj_surface
                    #            #print 'obj_width:', obj_width
                    #            #print 'odist:', odist
                    #            #print "slice drawn"
                    #            ##raw_input()
                                
            ray_angle -= self.ANGLE_BETWEEN_RAYS
        
        #if self.grid_surface_enabled: self.grid_surface = self.grid_surf_temp
        #if self.debug_points:
            #for i in xrange(len(self.debug_points)):
            #   self.draw_point_grid(self.debug_points[i], 6)
        
        if not somethingdraw: warn("Warning: No walls were drawn!")
        
        return True

   
    def vertical_intersect(self, pos, ray_angle):
        '''
        Returns vertical intersection  

        pos - tuple with player's x and y position
        ray_angle - current ray angle
        '''
        
        # * integer casts are for rounding down
          
        ray_facing_left = (90 < ray_angle < 270)
        ray_angle_rad = math.radians(ray_angle)

        # Finds the X of the first intersection point, then decides whether line belongs to left or right block, do not remove round down
        first_point_x = int(pos[0] / self.CUBE_SIZE) * self.CUBE_SIZE
        if ray_facing_left:
            first_point_x -= 1                  #belongs to left block
        else:
            first_point_x += self.CUBE_SIZE     #belongs to right block
        
        # Player Y plus the its distance to first intersection point, rounded down
        first_point_y_var = ( (pos[0] - first_point_x) * math.tan(ray_angle_rad) )
        first_point_y = int(pos[1] + first_point_y_var)
        
        # Is the first intersection point inside the world?
        firstpointgrid = self.togrid((first_point_x, first_point_y))
        if not Maps.is_valid_grid(firstpointgrid):
            return None

        # If there's a wall on the first point hit, return the position else continue searching for walls
        if self.wall_on(firstpointgrid): return (first_point_x, first_point_y)
        
        # Distance between subsequent intersection points
        
        # The y variation for the next intersections must have the same sign as the first point y variation
        y_variation = abs(int(self.CUBE_SIZE * math.tan(ray_angle_rad)))
        if first_point_y_var < 0:
            y_variation = -y_variation

        if ray_facing_left:
            x_variation = -self.CUBE_SIZE 
        else:
            x_variation = self.CUBE_SIZE
        
        # Search for a intersection point until grid index is out of bounds
        last_point = (first_point_x, first_point_y)
        
        while 1:
            next_point = (last_point[0] + x_variation, last_point[1] + y_variation)
            next_point_grid = self.togrid(next_point)
            
            if not Maps.is_valid_grid(next_point_grid):
                return None # reached end of the world without finding any walls

            if self.wall_on(next_point_grid):
                return next_point
            
            # This intersection point does not belong to a wall, proceed to next
            last_point = next_point

        
        assert 0, "Should not reach this point!"
    
    
    def horizontal_intersect(self, pos, ray_angle):
        '''
        Returns horizontal intersection  

        pos - tuple with player's x and y position
        ray_angle - current ray angle
        '''

        # * integer casts are for rounding down

        # There's no intersection if the ray is parallel to the horizontal grid lines
        if ray_angle in (0, 180):  return None
        
        ray_facing_up = (0 < ray_angle < 180)
        ray_angle_rad = math.radians(ray_angle)
        
        # Finds the Y of the first intersection point, then decides whether line belongs to upper or lower block, do not remove round down
        first_point_y = int(pos[1] / self.CUBE_SIZE) * self.CUBE_SIZE

        if ray_facing_up:
            first_point_y -= 1                   #belongs to upper block
        else:
            first_point_y += self.CUBE_SIZE      #belongs to lower block
        
        # Player X plus its the distance to first intersection point, rounded down
        first_point_x_var =  ( (pos[1] - first_point_y) / math.tan(ray_angle_rad) )
        first_point_x = int(pos[0] + first_point_x_var)
        
        firstpointgrid = self.togrid((first_point_x, first_point_y))
        # Is the first intersection point inside the world?
        if not Maps.is_valid_grid(firstpointgrid):
            return None
                                
        # If there's a wall on the first point hit, return the position else continue searching for walls
        if self.wall_on(firstpointgrid): return (first_point_x, first_point_y)

        # Distance between subsequent intersection points
        x_variation = abs(int(self.CUBE_SIZE / math.tan(ray_angle_rad)))
        if first_point_x_var < 0: #the sign of the 2nd variation MUST be the same as the 1st!
            x_variation = -x_variation

        if ray_facing_up:
            y_variation = -self.CUBE_SIZE 
        else:
            y_variation = self.CUBE_SIZE

        # Search for a intersection point until grid index is out of bounds
        last_point = (first_point_x, first_point_y) 
        while 1:
            next_point = (last_point[0] + x_variation, last_point[1] + y_variation)
            next_point_grid = self.togrid(next_point)

            if not Maps.is_valid_grid(next_point_grid):
                return None # reached end of the world without finding any walls

            if self.wall_on(next_point_grid):
                return next_point
            
            # This intersection point does not belong to a wall, proceed to next
            last_point = next_point

        
        assert 0, "Should not reach this point!"
        

                        

#DEBUG CODE
if __name__ == '__main__':
    import sys
    import random
    
    if len(sys.argv) < 2 or sys.argv[1] != "-profile":
        try:
            import psyco
            psyco.full()
        except ImportError:
            print "Performance Warning: psyco not available"
            pass
     
    
    class BloodDeath:
        def __init__(self):
            
            self.lengths = [0] * 640
            self.speeds = [random.randint(4,12) for i in xrange(640)]
            
        def draw(self, screen):
            for i in xrange(640):
                pygame.draw.line(screen, (152, 0, 0) , (i, 0), (i, self.lengths[i]) )
        
        def update(self):
            for i in xrange(640):
                if self.lengths[i] < 640:
                    self.lengths[i] += self.speeds[i]
                    

    bloodtest = BloodDeath()

    class PointOfView:
        def __init__(self, x=0, y=0, angle=0):
            self.x = x
            self.y = y
            self.angle = angle
            
        def turn_left(self, n):
            self.angle += n
            if self.angle > 359: self.angle = self.angle % 360

        def turn_right(self, n):
            self.angle -= n
            if self.angle < 0: self.angle = 360 - (abs(self.angle) % 360) #remainder behaviour is erratic with negative

        def walk_forward(self, n):
            self.x += n * math.cos(math.radians(self.angle))
            self.y -= n * math.sin(math.radians(self.angle))

        def walk_backward(self, n):
            self.x -= n * math.cos(math.radians(self.angle))
            self.y += n * math.sin(math.radians(self.angle))


    screen = None
    screenwidth = 640
    screenheight = 480
    projectionwidth = 640
    projectionheight = 480
    screenflags = 0
    #screenflags = pygame.FULLSCREEN
    screenbpp = 32

    fwspeed = 25
    turnspeed = 5

    # TESTING CODE
    def handle_input():
        for e in pygame.event.get():
            if e.type == pygame.QUIT:
                return False
            elif e.type == pygame.KEYDOWN:
                if e.key == pygame.K_ESCAPE:
                    return False
                elif e.key == pygame.K_LEFT:
                    pov.turn_left(2)
                elif e.key == pygame.K_RIGHT:
                    pov.turn_right(2)
                elif e.key == pygame.K_UP:
                    pov.walk_forward(3)
                elif e.key == pygame.K_DOWN:
                    pov.walk_backward(3)
        pygame.event.pump()
        
        keys = pygame.key.get_pressed()
        if keys[pygame.K_UP]:
            pov.walk_forward(fwspeed)
        if keys[pygame.K_LEFT]:
            pov.turn_left(turnspeed)
        if keys[pygame.K_RIGHT]:
            pov.turn_right(turnspeed)
        if keys[pygame.K_DOWN]:
            pov.walk_backward(fwspeed)
            
        return True



    print "Debugging session for Raycaster module."
   
    pygame.init()

    try:
        screen = pygame.display.set_mode((screenwidth, screenheight), screenflags , screenbpp) 
    except pygame.error, msg:   
        print "Error: failed to initialize display -", msg
     
    pygame.display.set_caption('Alien Xenocide - Ray Caster Demo')
    
    # Initialize Raycaster
    Raycaster = RaycasterClass(projectionwidth, projectionheight)
    
    pov = PointOfView(Raycaster.CUBE_SIZE*1.5, Raycaster.CUBE_SIZE*2.5, 65) # player's point of view

    # When accessing the world matrix use: world[y][x]
    # It may look as if it is backwards but y is the matrix line and x is the matrix column
    Maps.load_maps()
    Maps.set_current_map('map0')
    #Raycaster.load_world(world)
    Raycaster.toggle_textures(True)
    
    Raycaster.toggle_grid_surface(True) # set Raycaster to draw the 2D grid every frame with the walls hit
    #Raycaster.toggle_ray_debug_info(True) # set Raycaster to generate ray debug information
    
    class FPS_counter:
        def __init__(self):
            self.frames = 0
        def average(self):
            return self.frames / (pygame.time.get_ticks() / 1000.)  

    FPS = FPS_counter()
    myfont = pygame.font.SysFont("courier new", 14, False, False)
    
    Sprites.Sprites.load_sprites()
    myobjects = []
        
    while handle_input():
        screen.fill((0, 0, 0)) #clear screen
        Raycaster.render_scene(screen, pov, myobjects)
        #Raycaster.render_scene(screen, pov, [])
        if Raycaster.grid_surface_enabled: screen.blit(Raycaster.grid_surface, (0,0))
        
        #bloodtest.draw(screen)
        #bloodtest.update()
        
        #DEBUG
        fpstext = myfont.render("FPS: %d" % FPS.average(), False, (0,255,0)).convert()
        angletext = myfont.render("ANGLE: %3d" % pov.angle, False, (0,255,0)).convert()
        screen.blit(fpstext, (screenwidth - 83, 10))
        screen.blit(angletext, (screenwidth - 83, 25))
        pygame.display.flip()
        FPS.frames += 1
        #pygame.time.wait(10)
        

    # Save debug information
    #debugf = open("debugf.txt", 'w')
    #debugf.write(Raycaster.rays_info)
    #debugf.close()
    #if os.name == 'nt':
    #    pygame.image.save(Raycaster.grid_surface, "lastgridshot.png")
    #    os.system("start mspaint lastgridshot.png")
    #    os.system("start notepad debugf.txt")
    #else:
    #    pygame.image.save(Raycaster.grid_surface, "lastgridshot.tga")
    #    os.system("gimp lastgridshot.tga&")
    #    os.system("kedit debugf.txt&")
        
        
    pygame.quit()

    print "Thanks for playing Alien Xenocide."
